#ifndef LIST_HPP
#define LIST_HPP

#include <iostream>
#include <algorithm>
#include <string.h>

using namespace std;

namespace cs540{
	
template <typename T>
class Node{
	public:
		struct Node *next;
		struct Node *prev;

		Node(){
			next = NULL;
			prev = NULL;
		}
};

template <typename T>
class DNode: public Node<T> {
	public:
		T data;			// To hold the data
		DNode(T n):data(n){}
};

template <typename T>	
class List{

	public:
		/* Forward declerations */
		class Iterator;
		class ConstIterator;
		class ReverseIterator;

	private:
		Node<T> *m_sentinel;					// Sentinel Node 
		Node<T> *m_head;					// List head pointer
		Node<T> *m_tail;					// List tail pointer
		size_t m_size;						// Total number of elements

	public:
		List();
		List(const List &);					// Copy constructor 
		~List();						// Destructor
		Iterator begin();					// Return first element
		Iterator end();						// Return end element
		ConstIterator begin() const;				// Return first const element
		ConstIterator end() const;				// Return end const element
		ReverseIterator rbegin();				// Return ReverseIterator pointing to the beginning of the reversed list.
		ReverseIterator rend();					// Return ReverseIterator pointing to one past the last element of the reversed list.
		T &front();
		const T &front() const;
		T &back();
		const T &back() const;
		List &operator=(const List &);				// Assignment operator
		size_t size() const;					// Return Size
		Iterator insert (Iterator pos, const T &);		// Insert an element
		template <typename IT_T>
		void insert(Iterator pos, IT_T range_beg, IT_T range_end); // Insert range of elements into the List
		Iterator erase(Iterator pos);				// Erase an element from the List
		Iterator erase(Iterator range_beg, Iterator range_end); // Erase range of elements from the List
		void push_front(const T &);				// Push an element at front of the List
		void push_back(const T &);				// Push an element at back of the List
		void pop_front();					// Pop an element from front of the List
		void pop_back();					// Pop an element from end the List
		void clear();						// Clear the list
		void remove(const T &val);				// Remove all elements equal to 'val'
		void unique();						// Removes all contiguous, duplicate elements	
		void detach(List &, Iterator );				// Detach a node from the list
		void splice(Iterator dest_pos, List &src, Iterator src_pos); // Moves ele from src List to 'this' List
		void splice(Iterator dest_pos, List &src, Iterator range_beg, Iterator range_end);
		template<typename T1>
		friend List<T1> list_sort(List<T1> &lt);
		template<typename T1>
		friend bool operator==(const List<T1> &lt1, const List<T1> &lt2);
		template<typename T1>
		friend bool operator< (const List<T1> &lt1, const List<T1> &lt2);
	public: /* Nested classes */

		/* Iterator Class */
		class Iterator{
			public:
				Iterator();
				//Iterator(const Iterator &);
				//Iterator& operator=(const Iterator &);
				Iterator &operator++();
				Iterator operator++(int);
				Iterator &operator--();
				Iterator operator--(int);
				T &operator*() const;
				T *operator->() const;
				template<typename T1, typename T2>
				friend bool operator==(const T1 &, const T2 &);
				template<typename T1, typename T2>
				friend bool operator!=(const T1 &, const T2 &);
			public:
				Node<T> *m_node;
		};

		class ConstIterator: public Iterator{
			public:
				ConstIterator();
				//ConstIterator(const ConstIterator &);
				ConstIterator(const Iterator &);
				//ConstIterator& operator=(const ConstIterator &);
				ConstIterator &operator++();
				ConstIterator operator++(int);
				ConstIterator &operator--();
				ConstIterator operator--(int);
				const T &operator*() const;
				const T *operator->() const;
		};

		class ReverseIterator: public Iterator{
			public:
				ReverseIterator();
				//ReverseIterator(const ReverseIterator &);
				//ReverseIterator& operator=(const ReverseIterator &);
				ReverseIterator &operator++();
				ReverseIterator operator++(int);
				ReverseIterator &operator--();
				ReverseIterator operator--(int);
				T &operator*() const;
				T *operator->() const;
		};
};	

/******************** List ***************************/
template <typename T>
List<T> :: List(){
	m_sentinel = new Node<T>;
	/* Setup circular link list */
	m_sentinel->next = m_sentinel;
	m_sentinel->prev = m_sentinel;

	/* m_tail will always point to m_sentinel node. So no need to keep dummy pointer for interator end */
	m_head = m_tail = m_sentinel; 
	m_size = 0;
}

/* Copy constructor */
template <typename T>
List<T> :: List (const List & src){

	m_sentinel = new Node<T>;
	m_sentinel->next = m_sentinel;
	m_sentinel->prev = m_sentinel;

	m_head = m_tail = m_sentinel; 
	m_size = 0;

	List &ref_src = const_cast<List&> (src);
	Iterator s_it;

	for (s_it = ref_src.begin(); s_it != ref_src.end(); s_it++){
		push_back(*s_it);
	}
}

/* Destructor */
template <typename T>
List<T> :: ~List (){

	int i;
	Node<T> *tmp = m_head;
	Node<T> *t;
	while(tmp != m_tail){
		tmp->prev->next = tmp->next;
		tmp->next->prev = tmp->prev;
		t = tmp;
		tmp = tmp->next;	
		delete t;
		m_size --;
	}	
	delete m_sentinel;	
}

/* Normal begin */
template <typename T>
typename List<T>::Iterator List<T>::begin(){
	
	Iterator it;
	it.m_node = m_head;
	return it;
}

/* Normal end*/
template <typename T>
typename List<T>::Iterator List<T>::end(){
	
	Iterator it;
	it.m_node = m_tail; // TODO: Check if this is right
	return it;
}

/* Constant begin */
template <typename T>
typename List<T>::ConstIterator List<T>::begin() const {
	
	ConstIterator c_it;
	c_it.m_node = m_head;
	return c_it;
}

/* Constant end */
template <typename T>
typename List<T>::ConstIterator List<T>::end() const {
	
	ConstIterator c_it;
	c_it.m_node = m_tail; // TODO: Check if this is right
	return c_it;
}

/* Reverse begin */
template <typename T>
typename List<T>::ReverseIterator List<T>::rbegin() {
	
	ReverseIterator r_it;
	r_it.m_node = m_tail->prev;
	return r_it;
}

/* Reverse end */
template <typename T>
typename List<T>::ReverseIterator List<T>::rend() {
	
	ReverseIterator r_it;
	r_it.m_node = m_sentinel; // TODO: Check if this is right
	return r_it;
}

template <typename T>
T& List<T>::front(){

	return (static_cast<DNode<T> *>(m_head))->data;
}
	
template <typename T>
const T& List<T>::front() const{
	
	return (static_cast<DNode<T> *>(m_head))->data;
}
	
template <typename T>
T& List<T>::back(){

	return (static_cast<DNode<T> *>(m_tail->prev))->data;
}
	
template <typename T>
const T& List<T>::back() const{
	
	return (static_cast<DNode<T> *>(m_tail->prev))->data;
}

/* Assignment operator */
template <typename T>
List<T> & List<T> :: operator=(const List &src){
	
	Iterator it2;

	List &ref_src = const_cast<List&> (src);
	it2 = ref_src.begin();

	if (m_head != it2.m_node){
		
		/* Clear the list before assignment */
		clear(); 
		
		Iterator s_it;
		Iterator d_it;

		d_it.m_node = m_head;

		for (s_it = ref_src.begin(); s_it != ref_src.end(); s_it++){
			push_back(*s_it);
		}
	}
	return *this;
}

/* Return size */
template <typename T>
size_t List<T>::size() const{
	return m_size;
}

template <typename T>
typename List<T>::Iterator List<T>::insert(Iterator pos, const T &n){
		
	Iterator it;
	Node<T> *ele = new DNode<T>(n);

	if (m_head == m_sentinel) /* set new head & tail */
		m_head = ele;

	if (m_head == pos.m_node)
		m_head = ele;

	/* Insert before pos */
	ele->prev = pos.m_node->prev;
	ele->next = pos.m_node;
	pos.m_node->prev->next = ele;
	pos.m_node->prev = ele;

	/* Insert after pos */
	/*ele->next = pos.m_node->next;
	ele->prev = pos.m_node;
	pos.m_node->next = ele;
	ele->next->prev = ele;*/

	m_size ++;
	
	it.m_node = ele;
	return it;
}

/* Insert range of elements into the List */
template <typename T>
template <typename IT_T>
void List<T>::insert(Iterator pos, IT_T range_beg, IT_T range_end){ 

	for (; range_beg != range_end; range_beg++){
		insert(pos, *range_beg);
	}
}

template <typename T>
typename List<T>::Iterator List<T>::erase(Iterator pos){
		
	Iterator it;
	it.m_node = pos.m_node->next;

	if (pos.m_node == m_head){
		m_head = pos.m_node->next;
	}	

	pos.m_node->prev->next = pos.m_node->next;
	pos.m_node->next->prev = pos.m_node->prev;
	m_size--;

	delete pos.m_node;
	return it;
}

template <typename T>
typename List<T>::Iterator List<T>::erase(Iterator range_beg, Iterator range_end){
	
	for (; range_beg != range_end; ){
		range_beg = erase(range_beg);
	}
	return range_end;
}

template <typename T>
void List<T>::push_front(const T &n){

	Node<T> *ele = new DNode<T>(n);

	/* Insert before pos */
	ele->prev = m_head->prev;
	ele->next = m_head;
	m_head->prev->next = ele;
	m_head->prev = ele;

	m_head = ele;
	m_size++;
}

template <typename T>
void List<T>::push_back(const T &n){
	
	Node<T> *tmp = m_tail->prev;
	Node<T> *ele = new DNode<T>(n);

	/* Insert after pos */
	ele->next = tmp->next;
	ele->prev = tmp;
	tmp->next = ele;
	ele->next->prev = ele;

	if (m_size == 0)
		m_head = ele;
	m_size++;
}

template <typename T>
void List<T>::pop_front(){
	
	Node<T> *tmp = m_head;
	m_head = m_head->next;

	tmp->prev->next = tmp->next;
	tmp->next->prev = tmp->prev;
	tmp->prev = tmp->next = 0;

	m_size--;
	delete tmp;
}

template <typename T>
void List<T>::pop_back(){
	
	Node<T> *tmp = m_tail->prev;
	tmp->prev->next = tmp->next;
	tmp->next->prev = tmp->prev;

	m_size--;
	if (m_size == 0)
		m_head = m_sentinel;

	delete tmp;
}

template <typename T>
void List<T>::clear(){

	while( m_size != 0){
		pop_back();
	}
}

template <typename T>
void List<T>::remove(const T &val){
	
	Node<T> *tmp = m_head;
	Node<T> *t;
	
	while(tmp != m_tail){
		if ((static_cast<DNode<T> *>(tmp))->data == val){

			if (tmp == m_head) /* check if m_head contains the required data */
				m_head = tmp->next;
			
			tmp->prev->next = tmp->next;
			tmp->next->prev = tmp->prev;
			t = tmp;
			tmp = tmp->next;

			delete t;
		
			m_size--;
		}
		else
			tmp = tmp->next;
	}

	if (m_size == 0)
		m_head = m_sentinel;
}

template <typename T>
void List<T>::unique(){
	
	Node<T> *tmp = m_head;
	Node<T> *t = NULL;
	Node<T> *t1 = NULL;
	
	while(tmp != m_tail){
		while ((tmp->next != m_tail) && ((static_cast<DNode<T> *>(tmp))->data ==  static_cast<DNode<T> *>(tmp->next)->data)) {
			t = tmp->next;
			t->prev->next = t->next;
			t->next->prev = t->prev;
			t1 = t;
			t = t->next;

			delete t1;
			m_size--;
		}
		tmp = tmp->next;
	}
}

/* This is internal function used to detach a node from the list.
   This operation will not free the node.
*/
template <typename T>
void List<T>::detach(List<T> &src, Iterator src_pos){

	if (m_head == src_pos.m_node)
		m_head = src_pos.m_node->next;

	src_pos.m_node->prev->next = src_pos.m_node->next;
	src_pos.m_node->next->prev = src_pos.m_node->prev;
	m_size--;
}

template <typename T>
void List<T>::splice(Iterator dest_pos, List &src, Iterator src_pos){
	
	src.detach(src, src_pos);

	if (dest_pos.m_node == m_head)
		m_head = src_pos.m_node;
		
	/* Insert before pos */
	src_pos.m_node->prev = dest_pos.m_node->prev;
	src_pos.m_node->next = dest_pos.m_node;
	dest_pos.m_node->prev->next = src_pos.m_node;
	dest_pos.m_node->prev = src_pos.m_node;

	m_size++;
}

template <typename T>
void List<T>::splice(Iterator dest_pos, List &src, Iterator range_beg, Iterator range_end){
	
	Iterator it = range_beg;
	while (range_beg != range_end){
		splice(dest_pos, src, range_beg++);
	}
}

template <typename T>
bool operator==(const List<T> &lt1, const List<T> &lt2){


	List<T> &ref_lt1 = const_cast<List<T>&> (lt1);
	List<T> &ref_lt2 = const_cast<List<T>&> (lt2);
	
	if (lt1.size() == lt2.size()){
		typename List<T>::Iterator it1 = ref_lt1.begin();
		typename List<T>::Iterator it2 = ref_lt2.begin();

		for (; it1 != ref_lt1.end(); it1++, it2++){
				
			if (*it1 != *it2){
				return false;
			}	
		}
	}
	else
		return false;
	
	return true;
}

template <typename T>
List<T> list_sort(List<T> &lt){

	if (lt.size() > 1){
		typename List<T>::Iterator it = lt.begin();
		typename List<T>::Iterator it1 = lt.begin();
		typename List<T>::Iterator tmp ;

		it++;
		for ( ; it != lt.end(); it++){
			it1 = lt.begin();
			while(it != it1){
				if (*it1 < *it){
					it1++;	
				}
				else{
					if(lt.m_head == it1.m_node)
						lt.m_head = it.m_node;

					tmp = it;
					it1.m_node->prev->next = it.m_node;
					it.m_node->next->prev = it1.m_node;
					it1.m_node->next = it.m_node->next;
					it.m_node->next = it1.m_node;
					it.m_node->prev = it1.m_node->prev;
					it1.m_node->prev = it.m_node;
					it = it1;
					break;
				}
			}
		}		
	}
	return lt;
}


template <typename T>
bool operator<(const List<T> &lt1, const List<T> &lt2){

	if (lt1.size() <= lt2.size()){
		List<T> tmp1 (lt1);
		List<T> tmp2 (lt2);
		typename List<T>::Iterator it1 = tmp1.begin();
		typename List<T>::Iterator it2 = tmp1.begin();

		for(it1 = tmp1.begin(), it2 = tmp2.begin(); it1 != tmp1.end() && it2 != tmp2.end(); it1++, it2++){

			if (*it1 == *it2){
				continue;
			}
			else if (*it1 < *it2){
					return true;
			}
			else{
				return false;
			}	
		}
		if (it1 == tmp1.end() && it2 != tmp2.end())
			return true;
		else	
			return false;
	}
	else
		return false;
}

/***************************************** Iterator *****************************************/

/* Iterator constructor */
template <typename T>
List<T>::Iterator::Iterator(){
	m_node = NULL;
}

/*
template <typename T>
List<T>::Iterator::Iterator(const Iterator &it) {

	cout << "Iterator Param Ctor\n";
	m_node = new Node<T>;

	memcpy (m_node, it.m_node, sizeof(Node<T>));
	
}


template <typename T>
typename List<T>::Iterator & List<T>::Iterator::operator=(const Iterator &){
	
	cout << "Iterator operator=\n";
	return *this;
}
*/

template <typename T>
typename List<T>::Iterator & List<T>::Iterator::operator++(){

	this->m_node = m_node->next;
	return *this;
}

template <typename T>
typename List<T>::Iterator List<T>::Iterator::operator++(int){

	Iterator it = *this;
	this->m_node = m_node->next;
	return it;
}

template <typename T>
typename List<T>::Iterator & List<T>::Iterator::operator--(){

	Iterator it;
	this->m_node = m_node->prev;
	return *this;
}

template <typename T>
typename List<T>::Iterator List<T>::Iterator::operator--(int){

	Iterator it = *this;
	this->m_node = m_node->prev;
	return it;
}

template <typename T>
T& List<T>::Iterator::operator*() const{

	return (static_cast<DNode<T> *>(m_node))->data;
}

template <typename T>
T* List<T>::Iterator::operator->() const{

	return &(static_cast<DNode<T> *>(m_node))->data;
}

template <typename T1, typename T2>
bool operator==(const T1 &it1, const T2 &it2){
	if (it1.m_node == it2.m_node)
		return true;
	else
		return false;
}

template <typename T1, typename T2>
bool operator!=(const T1 &it1, const T2 &it2){

	return !(it1 == it2);
}

/***************************************** ConstIterator *****************************************/
template <typename T>
List<T>::ConstIterator::ConstIterator(){
	
}

/* Const Conversion operator */
template <typename T>
List<T>::ConstIterator::ConstIterator(const Iterator &it){
	this->m_node = it.m_node;
}

template <typename T>
typename List<T>::ConstIterator & List<T>::ConstIterator::operator++(){

	this->m_node = this->m_node->next;
	return *this;
}

template <typename T>
typename List<T>::ConstIterator List<T>::ConstIterator::operator++(int){

	ConstIterator it = *this;
	this->m_node = this->m_node->next;
	return it;
}

template <typename T>
typename List<T>::ConstIterator & List<T>::ConstIterator::operator--(){

	ConstIterator it;
	this->m_node = this->m_node->prev;
	return *this;
}

template <typename T>
typename List<T>::ConstIterator List<T>::ConstIterator::operator--(int){

	ConstIterator it = *this;
	this->m_node = this->m_node->prev;
	return it;
}

template <typename T>
const T& List<T>::ConstIterator::operator*() const{

	return (static_cast<DNode<T> *>(this->m_node))->data;
}

template <typename T>
const T* List<T>::ConstIterator::operator->() const{

	return &(static_cast<DNode<T> *>(this->m_node))->data;
}


/***************************************** ReverseIterator *****************************************/

template <typename T>
List<T>::ReverseIterator::ReverseIterator(){
}

template <typename T>
typename List<T>::ReverseIterator & List<T>::ReverseIterator::operator++(){

	ReverseIterator it;
	this->m_node = this->m_node->prev;
	return *this;
}

template <typename T>
typename List<T>::ReverseIterator List<T>::ReverseIterator::operator++(int){

	ReverseIterator it = *this;
	this->m_node = this->m_node->prev;
	return it;
}

template <typename T>
typename List<T>::ReverseIterator & List<T>::ReverseIterator::operator--(){

	ReverseIterator it;
	this->m_node = this->m_node->next;
	return *this;
}

template <typename T>
typename List<T>::ReverseIterator List<T>::ReverseIterator::operator--(int){

	ReverseIterator it = *this;
	this->m_node = this->m_node->next;
	return it;
}

template <typename T>
T& List<T>::ReverseIterator::operator*() const{

	return (static_cast<DNode<T> *>(this->m_node))->data;
}

template <typename T>
T* List<T>::ReverseIterator::operator->() const{

	return &(static_cast<DNode<T> *>(this->m_node))->data;
}


} // namespace cs540

#endif // #ifndef LIST_HPP
